#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>

using namespace std;

namespace lh
{ 
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    //层次遍历
    void traverse(TreeNode* root, vector<vector<int>>& res, int depth)
    {
        if (root == nullptr)
            return;
        if (res.size() < depth)
        {
            res.push_back(vector<int>{});
        }
        res[depth - 1].push_back(root->val);
        traverse(root->left, res, depth + 1);
        traverse(root->right, res, depth + 1);
    }
    vector<vector<int> > levelOrder(TreeNode* root) {
        vector<vector<int>>res;
        if (root == nullptr)
            return res;
        traverse(root, res, 1);
        return res;
    }
    //BM28 二叉树的最大深度
    //https://www.nowcoder.com/practice/8a2b2bf6c19b4f23a9bdb9b233eefa73?tpId=295&tqId=642&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution1 {
    public:
        int maxDepth(TreeNode* root) {
            if (root == nullptr)
                return 0;
            return max(maxDepth(root->left), maxDepth(root->right)) + 1;
        }
    };
    void test1()
    {
        TreeNode* root = new TreeNode(1);
        TreeNode* node2 = new TreeNode(2);
        TreeNode* node3 = new TreeNode(3);
        TreeNode* node4 = new TreeNode(4);
        TreeNode* node5 = new TreeNode(5);

        root->left = node2;
        root->right = node3;
        node2->left = node4;
        node3->right = node5;
        cout << "BM28 二叉树的最大深度:" << endl;
        cout << Solution1().maxDepth(root) << endl;
        
        delete root;
        delete node2;
        delete node3;
        delete node4;
        delete node5;

    }

    //BM29 二叉树中和为某一值的路径(一)
    //https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c?tpId=295&tqId=634&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution2 {
    public:
        bool hasPathSum(TreeNode* root, int sum) {
            //前序遍历查找
            if (root == nullptr)
            {
                return false;
            }
            //叶子节点
            if (root->left == nullptr && root->right == nullptr && sum - root->val == 0)
            {
                return true;
            }
            return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);

        }
    };
    void test2()
    {
        TreeNode* root = new TreeNode(5);
        TreeNode* node2 = new TreeNode(4);
        TreeNode* node3 = new TreeNode(8);
        TreeNode* node4 = new TreeNode(1);
        TreeNode* node5 = new TreeNode(11);
        TreeNode* node6 = new TreeNode(9);
        TreeNode* node7 = new TreeNode(2);
        TreeNode* node8 = new TreeNode(7);
        root->left = node2;
        root->right = node3;
        node2->left = node4;
        node2->right = node5;
        node5->left = node7;
        node5->right = node8;
        node3->right = node6;
        cout << "BM29 二叉树中和为某一值的路径(一):" << endl;
        cout << Solution2().hasPathSum(root, 22) << endl;

        delete root;
        delete node2;
        delete node3;
        delete node4;
        delete node5;
        delete node6;
        delete node7;
        delete node8;

    }
    //BM31 对称二叉树
    //https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=295&tqId=23452&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution3 {
    public:
        bool recursion(TreeNode* root1, TreeNode* root2)
        {
            //都为空结点（暂时对称）
            if (root1 == nullptr && root2 == nullptr)
                return true;
            //只有1个结点为空或者2个结点值不相同，必定不对称
            if (root1 == nullptr || root2 == nullptr || root1->val != root2->val)
                return false;
            //每层结点进入递归比较
            return recursion(root1->left, root2->right) && recursion(root1->right, root2->left);
        }
        bool isSymmetrical(TreeNode* pRoot) {
            //思路：同时遍历“根左右”和“根右左”，比较同时遍历时的结点是否相同
            //"根左右"走左时，"根右左"走右。"根左右"走右时，"根右左"走左。
            return recursion(pRoot, pRoot);
        }
    };
    void test3()
    {
        TreeNode* root = new TreeNode(1);
        TreeNode* node2 = new TreeNode(2);
        TreeNode* node3 = new TreeNode(2);
        TreeNode* node4 = new TreeNode(3);
        TreeNode* node5 = new TreeNode(4);
        TreeNode* node6 = new TreeNode(4);
        TreeNode* node7 = new TreeNode(3);
        root->left = node2;
        root->right = node3;
        node2->left = node4;
        node2->right = node5;
        node3->left = node6;
        node3->right = node7;
        cout << "BM31 对称二叉树:" << endl;
        cout << Solution3().isSymmetrical(root) << endl;
        delete root;
        delete node2;
        delete node3;
        delete node4;
        delete node5;
        delete node6;
        delete node7;
    }

    //BM32 合并二叉树
    //https://www.nowcoder.com/practice/7298353c24cc42e3bd5f0e0bd3d1d759?tpId=295&tqId=1025038&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution4 {
    public:

        TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
            //根左右方式遍历
            //如果一个为空，则返回另一个，若两个都为空自然返回null
            if (!t1)
                return t2;
            if (!t2)
                return t1;
            //均不为空
            TreeNode* head = new TreeNode(t1->val + t2->val);
            head->left = mergeTrees(t1->left, t2->left);
            head->right = mergeTrees(t1->right, t2->right);
            return head;
        }
    };
    void test4()
    {
        TreeNode* root = new TreeNode(1);
        TreeNode* node2 = new TreeNode(3);
        TreeNode* node3 = new TreeNode(2);
        TreeNode* node4 = new TreeNode(5);
        root->left = node2;
        root->right = node3;
        node2->left = node4;
        
        TreeNode* _root = new TreeNode(2);
        TreeNode* _node2 = new TreeNode(1);
        TreeNode* _node3 = new TreeNode(3);
        TreeNode* _node4 = new TreeNode(4);
        TreeNode* _node5 = new TreeNode(7);
        _root->left = _node2;
        _node2->right = _node4;
        _root->right = _node3;
        _node3->right = _node5;
        cout << "BM32 合并二叉树:" << endl;
        TreeNode* head = Solution4().mergeTrees(root, _root);
        vector<vector<int>>res;
        res = levelOrder(head);
        for (int i = 0; i < res.size(); i++)
        {
            for (int j = 0; j < res[i].size(); j++)
            {
                cout << res[i][j] << " ";
            }
        }
        delete root;
        delete node2;
        delete node3;
        delete node4;
        delete _root;
        delete _node2;
        delete _node3;
        delete _node4;
    }
}

int main()
{
    lh::test1();
    lh::test2();
    lh::test3();
    lh::test4();
    return 0;
}